'''
https://leetcode.cn/problems/merge-two-sorted-lists/description/
'''
from typing import Optional
from utils import *


class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1: return list2
        if not list2: return list1
        new_list = ListNode(-1)
        cur = new_list
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        if list1:
            cur.next = list1
        if list2:
            cur.next = list2
        return new_list.next


l1 = ListNode(val=1)
l2 = ListNode(val=2)
l3 = ListNode(val=3)
l1.next = l2
l2.next = l3

l4 = ListNode(val=1)
l5 = ListNode(val=2)
l6 = ListNode(val=5)
l4.next = l5
l5.next = l6

new_list = Solution().mergeTwoLists(l1, l4)
print_list(new_list)